package 回溯.不熟;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 删除无效的括号301.java
 * @createTime 2022年12月30日 16:07:00
 */
public class 删除无效的括号301 {
	public static void main(String[] args) {
		removeInvalidParentheses(")(");
	}


	static List<String> result = new ArrayList<>();

	public static List<String> removeInvalidParentheses(String s) {
		//先计算左右括号的数量
		int leftNum = 0, rightNum = 0;
		LinkedList<Character> list = new LinkedList<>();
		for (int i = 0; i < s.length(); i++) {
			list.add(s.charAt(i));
			char c = s.charAt(i);
			if (c == '(') {
				leftNum++;
			} else if (c == ')') {
				rightNum++;
			}
		}
		backTrace(list, s, 0, leftNum, rightNum);
		return result;
	}

	public static void backTrace(LinkedList<Character> chars, String s, int curIndex, int leftNum, int rightNum) {
		//左括号跟右括号数量相等
		if (leftNum == rightNum) {
			if (isValid(chars)) {
				StringBuilder sb = new StringBuilder();
				for (Character character : chars) {
					sb.append(character);
				}
				result.add(sb.toString());
			}
			return;
		}
		for (int i = curIndex; i < chars.size(); i++) {
			char c = chars.get(i);
			//如果是去除左括号
			if (c == '(') {
				//去除左括号
				chars.remove(i);
				backTrace(chars, s, i + 1, leftNum - 1, rightNum);
				//不去除
				chars.add(i, '(');
				backTrace(chars, s, i + 1, leftNum, rightNum);
			} else if (c == ')') {
				//去除左括号
				chars.remove(i);
				backTrace(chars, s, i + 1, leftNum, rightNum - 1);
				//不去除
				chars.add(i, ')');
				backTrace(chars, s, i + 1, leftNum, rightNum);
			} else {
				backTrace(chars, s, i + 1, leftNum, rightNum);
			}
		}
	}

	private static boolean isValid(LinkedList<Character> s) {
		int conut = 0;
		for (Character ch : s) {
			if (ch == '(') {
				conut++;
			} else if (ch == ')') {
				if (conut == 0) {
					return false;
				}
				conut--;
			}
		}
		return conut == 0;
	}
}
